package com.zjsru.oneDay202205;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/5/14
 *  贴纸拼词
 *  您想要拼写出给定的字符串 target ，方法是从收集的贴纸中切割单个字母并重新排列它们。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。
 *
 *  输入： stickers = ["with","example","science"], target = "thehat"
 * 输出：3
 * 解释：
 * 我们可以使用 2 个 "with" 贴纸，和 1 个 "example" 贴纸。
 * 把贴纸上的字母剪下来并重新排列后，就可以形成目标 “thehat“ 了。
 * 此外，这是形成目标字符串所需的最小贴纸数量。
 *
 */
public class minStickers {
    int N = 20, M = 1<<20, INF = 50;
    int[] f = new int[this.M];
    String[] ss;
    String t;
    int dfs(int state){
        int n = this.t.length();
        if (state == ((1 << n) - 1)) {
            return 0;
        }
        if (this.f[state] != -1) {
            return this.f[state];
        }
        int ans = this.INF;
        for (String s : this.ss) {
            int nstate = state;
            out:for (char c: s.toCharArray()){
                for (int i = 0; i < n; i++) {
                    if (this.t.charAt(i) == c && ((nstate >> i) & 1) == 0) {
                        nstate |= (1 <<i);
                        continue out;
                    }
                }
            }
            if (nstate != state) {
                ans = Math.min(ans, this.dfs(nstate) + 1);
            }
        }
        return this.f[state] = ans;
    }
    public int minStickers(String[] stickers, String target) {
        this.ss = stickers;
        this.t = target;
        Arrays.fill(this.f, -1);
        int ans = this.dfs(0);
        return ans == this.INF ? -1 : ans;
    }
    
    public static void main(String[] args) {
        minStickers minStickers = new minStickers();
        String[] stickers = new String[]{"with","example","science"};
        String target = "thehat";
        System.out.println(minStickers.minStickers(stickers, target));
    }
}
